package com.test27_二叉树.util;

public class BinaryTreeMapImpl<K, V> implements IMap<K, V> {
    /** 树结构存储的包装类 */
    private class Entry<K, V> implements Comparable<Entry<K, V>> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(Entry<K, V> o) {   // 所有的数据依据key实现排序操作
            return ((Comparable) this.key).compareTo(o.key);
        }
    }

    /** 节点类 */
    private class Node {
        private Entry<K, V> data;
        private Node left;
        private Node right;

        public Node(Entry<K, V> data) {
            this.data = data;
        }

        /** 递归方式实现节点存储 */
        public V addNode(Node newNode) {
            if (this.data.compareTo(newNode.data) < 0) {    // 新的内容大于根节点
                if (this.right == null) {
                    this.right = newNode;
                } else {
                    return this.right.addNode(newNode);
                }
            } else if (this.data.compareTo(newNode.data) > 0) { // 新的内容小于根节点
                if (this.left == null) {
                    this.left = newNode;
                } else {
                    return this.left.addNode(newNode);
                }
            } else {    // key存在
                V old = this.data.value;
                this.data.value = newNode.data.value;
                return old;     // 返回旧数据
            }
            return null;
        }

        public V getNode(K key) {
            if (this.data.key.equals(key)) {
                return this.data.value;
            } else {
                if (((Comparable) this.data.key).compareTo(key) <= 0) {
                    if (this.right != null) {
                        return this.right.getNode(key);
                    }
                } else {
                    if (this.left != null) {
                        return this.left.getNode(key);
                    }
                }
            }
            return null;
        }
    }

    // ================= 以下为接口实现类的处理 =================
    private Node root;  // 根节点
    private int count;  // 保存元素个数

    /**
     * 保存数据内容
     * @return 返回上次存储的内容
     */
    @Override
    public V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("保存数据的key或value不允许为空！");
        }
        if (!(key instanceof Comparable)) {
            throw new ClassCastException("作为key的所在类必须实现Comparable接口！");
        }
        Entry<K, V> entry = new Entry<>(key, value);
        Node newNode = new Node(entry);
        this.count++;
        if (this.root == null) {
            this.root = newNode;
            return null;
        } else {
            return this.root.addNode(newNode);
        }
    }

    /** 根据key查询value */
    @Override
    public V get(K key) {
        if (key == null) {
            throw new NullPointerException("查询数据的key不允许为空！");
        }
        if (!(key instanceof Comparable)) {
            throw new ClassCastException("作为key的所在类必须实现Comparable接口！");
        }
        if (this.root == null) {
            return null;
        }
        return this.root.getNode(key);
    }

    /** 获取元素个数 */
    @Override
    public int size() {
        return this.count;
    }
}
